home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / snippet.exe / RAND3.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-25  |  2.1 KB  |  45 lines
  1. /*
  2.  This type of random generators originate in early 1950's, and their
  3.  good properties were well known by late 50's (cf. D.Knuth 2nd ed.,
  4.  vol 2, section 3.2.2). A table of 90 different "magic pairs" like (97,23) 
  5.  is also given in Knuth, as well as generalizations of the simple add to 
  6.  primitive polynomials as suggested in your message.
  7.  
  8.  As for practical implementations on a micro, the floating point version
  9.  will be very slow compared to integer version (even with 8087). I've
  10.  actually used exactly the same pair (97,23) combined with lookup based
  11.  CRC-16 instead of an add to obtain very fast and practically unlimited 
  12.  source for random numbers. One should note that to obtain floating point
  13.  sequence, it is not enough to concatenate succesive random numbers from
  14.  the say 16-bit integer generator. Instead one should use 32-bit integers
  15.  or 64-bit integers for float/double (best done in assembler), with proper
  16.  range reduction on the exponent part (usually just an AND/OR mask). As to
  17.  seeding of the array[97], one can use rand() coupled with time/date
  18.  functions as suggested in several other responses. I've used PC timer
  19.  8253 directly which runs at 1.19 Mhz, coupled with date and keyboard 
  20.  interrupt, the array is re-seeded by adding new-seed-rand() values to
  21.  the existent ones whenever a key was struck. Also, the random numbers
  22.  are continuously generated in any program-idle state.
  23.  
  24.  The core of the algorithm (without CRC and seed generator) is:
  25. */
  26.  /********************************************************************
  27.   Random Array ra[] is initialized to not-all-even, with e.g. rand()
  28.   coupled with time/date. Before using the numbers, few thousands 
  29.   (+/-  random number) should be generated and discarded.
  30.  ********************************************************************/
  31.  
  32.  typedef unsigned int rn;
  33.  #define RA_TOP (ra+96)
  34.  
  35.  rn ra[97]; 
  36.  rn *p97=RA_TOP, *p23=ra+22;
  37.  
  38.  rn fast_rnd()
  39.  { rn r;
  40.      r = (*p97-- += *p23--);
  41.      if (p97 < ra) p97=RA_TOP;
  42.        else if (p23 < ra) p23=RA_TOP;
  43.      return(r);
  44.  }
  45.